home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group98a.txt / 000128_icon-group-sender _Fri Mar 13 08:07:45 1998.msg < prev    next >
Internet Message Format  |  2000-09-20  |  3KB
  1. Return-Path: <icon-group-sender>
  2. Received: from kingfisher.CS.Arizona.EDU (kingfisher.CS.Arizona.EDU [192.12.69.239])
  3.     by baskerville.CS.Arizona.EDU (8.8.7/8.8.7) with SMTP id IAA23735
  4.     for <icon-group-addresses@baskerville.CS.Arizona.EDU>; Fri, 13 Mar 1998 08:07:44 -0700 (MST)
  5. Received: by kingfisher.CS.Arizona.EDU (5.65v4.0/1.1.8.2/08Nov94-0446PM)
  6.     id AA17073; Fri, 13 Mar 1998 08:07:44 -0700
  7. Message-Id: <35089F74.6018@gte.net>
  8. Date: Thu, 12 Mar 1998 20:52:36 -0600
  9. From: Mark Evans <evans@gte.net>
  10. Reply-To: evans@gte.net
  11. Organization: None
  12. X-Mailer: Mozilla 3.01 (Win95; I)
  13. Mime-Version: 1.0
  14. To: icon-group@optima.CS.Arizona.EDU
  15. Cc: evans@gte.net
  16. Subject: Letter Probabilities
  17. References: <Pine.SOL.3.96.980312052940.7871A-100000@post.its.mcw.edu> <350813B6.503F@gte.net> <35089EC7.49D@gte.net>
  18. Content-Type: text/plain; charset=us-ascii
  19. Content-Transfer-Encoding: 7bit
  20. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  21. Status: RO
  22. Content-Length: 1743
  23.  
  24. Here is a small Icon problem related to letter probabilites.  Each
  25. letter has a "probability of occurrence" in the information-theoretic
  26. setting.  This probability can be estimated from sample texts.  I want
  27. to generate random text based on these probabilities.
  28.  
  29. I have a table that associates inidividual letters (one-char strings)
  30. with real numbers (probabilities).  We can assume for the sake of
  31. argument that the sum of all probabilities in my table is unity.
  32.  
  33. Given this table (which I already have Icon code to obtain) what is the
  34. most efficient method of generating random text?  What I am thinking of
  35. at the moment is:
  36.  
  37. (1) get a sorted list of [key,value] pairs,
  38.        sorted by value (probability),
  39.        highest probability first
  40.  
  41. (2) generate a random number from 0.0 to 1.0
  42.  
  43. (3) use a while-loop to find the slot in the
  44.        sorted list where the number falls;
  45.        I would subtract each passing probability
  46.        until my placeholder value had vanished; e.g.
  47.  
  48.        i := 0   # running index
  49.        x := ?0  # random number 0.0 - 1.0
  50.        while x > 0 do
  51.        {
  52.           i +:= 1
  53.           x -:= prob_list[i][2]
  54.        }
  55.        letter := prob_list[i][1]
  56.  
  57.  
  58.  
  59. This all seems rather awkward to me, especially step (3).  Isn't there
  60. some construct in Icon that could do this more elegantly?  Some way to
  61. search a list for a pair of elements that bracket a variable value?
  62.  
  63. Mark
  64.  
  65. P.S.  I am already very well acquainted with the sample program
  66. 'monkeys.icn' in the distribution.  This program uses multiple-character
  67. sequences, not individual letter probabilities.  More characters gives a
  68. better approximation to the source language, but I am interested
  69. specifically in single-character probabilities right at the moment.
  70.  
  71.